1. geneticData
NAm2 = read.table("NAm2.txt", header = TRUE)
# unique is used to get the name of all population / ethnics without duplicates
names=unique(NAm2$Pop)
npop=length(names)
# coordinates for each pop
coord=unique(NAm2[, c("Pop","long","lat")])
colPalette=rep(c("black","red","cyan","orange","brown","blue","pink","purple","darkgreen"),3)
# type 16 = circle / type 15 = square / type 25 = triangle
pch=rep(c(16,15,25),each=9)
# the display works because for each population we have the latitude and the longitude
plot(coord[, c("long","lat")],pch=pch,col=colPalette,asp=1)
# asp allows to have the correct ratio between axis longitude and latitude
# Then the map is not deformed
legend("bottomleft",legend=names,col=colPalette,lty=-1,pch=pch,cex=.75,ncol=2,lwd=2)
library(maps);map("world",add=T)

The description of the script is in the commentaries above.
2. Regression
# turn the matrix into a geneticData frame
geneticData = NAm2[,-c(1:7)]
geneticDataFrame = data.frame(geneticData)
# creation of the linear model
reg = lm(formula = long ~ . , data = geneticDataFrame)
# uncomment that following part to see the summary of the regression
# summary(reg)
All values are NA (Not Available) because we have too much predictors. The \(X\) matrix is cannot be reversed so we have to use the PCA method to counter that problem.
3.PCA Principal Component Analysis
a)
The main goal of the PCA is to reduce the number of predictors. In order to achieve that, we have to extract the most important components of the geneticData set. These new variables are a linear combinaison of the original ones. The number of principal components is smaller than the number of original variables. The aim is to maximize the variation of the geneticData set.
b)
# install.packages("factoextra")
library(factoextra)
Loading required package: ggplot2
Welcome! Related Books: `Practical Guide To Cluster Analysis in R` at https://goo.gl/13EFCZ
allGenes <- geneticDataFrame[, -1]
pcaNAm2 <- prcomp(allGenes, scale = FALSE)
fviz_eig(pcaNAm2)

vectProportionOfVariance <- pcaNAm2$sdev^2/sum(pcaNAm2$sdev^2)
# summary(pcaNAm2.pca)
It is better to use scale = FALSE by convention because we get a better representation of the percentage of explained values.
FALSE : 494 = linear combianison of the 5000 genes We notice that we get only 494 principal components instead of approximately 5000 which correspond to the number of genes. This can be explained because “” in the covariance matrix the eigenvalues from 495 to ~5000 are equals to zero. In reality, we only select the genes that best explain the model up to 500. If we had to really find the “best-explaining”, which means finding the most explicative genes from 1 to 5000 we would have to test all the combinaisons of 494 genes.
c)
caxes=c(1,2)
plot(pcaNAm2$x[,caxes],col="white")
for (i in 1:npop) {
# print(names[i])
lines(pcaNAm2$x[which(NAm2[,3]==names[i]),caxes],
type="p",col=colPalette[i],pch=pch[i])
}
legend("topleft",legend=names,col=colPalette,lty=-
1,pch=pch,cex=.65,ncol=3,lwd=2)

caxes=c(5,6)
plot(pcaNAm2$x[,caxes],col="white")
for (i in 1:npop) {
# print(names[i])
lines(pcaNAm2$x[which(NAm2[,3]==names[i]),caxes],
type="p",col=colPalette[i],pch=pch[i])
}
legend("topright",legend=names,col=colPalette,lty=-
1,pch=pch,cex=.65,ncol=3,lwd=2)

The Ache population is well identified by both components. The Surui can also be identified by both components but more especially by the PC1.
The Karitiana population is well identified by the PC5. The Pima population is well identified by the PC6.
d)
inertia = vectProportionOfVariance[1] + vectProportionOfVariance[2]
sprintf("The inertia is equal to %f.", inertia)
[1] "The inertia is equal to 0.035684."
According to what we have seen until now, we have two ideas.
The first idea is that we have seen that we can distinguish two population using two principal components. Therefore, as there are 27 different populations, we could deduce that we would need 14 pairs of principal components.
However, we can ask ourselves if we can really each time distinguish two different populations using two principal components. It might not be the case because we have just tested it with two pairs of principal components. Thus, we could think about an alternative way, which is adding the variance of the first principal components until the sum is equal to a certain level. This level could be 25% or 50%. This last one means using a lot of principal components.
numberOfPCs <- function(vectorProportionOfVariance, percentage) {
tmp = 0.0
i = 1
while (tmp < percentage) {
tmp = tmp + vectProportionOfVariance[i]
i = i + 1
}
return(i)
}
nbrPC25 <- numberOfPCs(vectProportionOfVariance, 0.25)
nbrPC50 <- numberOfPCs(vectProportionOfVariance, 0.5)
nbrPC75 <- numberOfPCs(vectProportionOfVariance, 0.75)
nbrPC99 <- numberOfPCs(vectProportionOfVariance, 0.99)
sprintf("Number of principal components needed in order to cover at least 25 percent of variance : %i", nbrPC25)
[1] "Number of principal components needed in order to cover at least 25 percent of variance : 40"
sprintf("Number of principal components needed in order to cover at least 50 percent of variance : %i", nbrPC50)
[1] "Number of principal components needed in order to cover at least 50 percent of variance : 120"
sprintf("Number of principal components needed in order to cover at least 75 percent of variance : %i", nbrPC75)
[1] "Number of principal components needed in order to cover at least 75 percent of variance : 240"
sprintf("Number of principal components needed in order to cover at least 99 percent of variance : %i", nbrPC99)
[1] "Number of principal components needed in order to cover at least 99 percent of variance : 473"
With the test we have established just before we can see that less than \(1/10\) of the data contains \(25%\) of the variance : So it seems like a good idea to use only \(50\) PC to get most of the information within least data. So we might use that number of PC in order to represent genetic markers. The other numbers give a idea of the number needed if we want to cover more information.
4. PCR Principal Components Regression
a)
# pcaNAm2$x are scores : size 494 * 494 matrix. We take all the ligns but only 250 columns
first250PCs <- pcaNAm2$x[, c(1:250)]
# size 494 * 251 => first column become the longitude
long <- c(NAm2$long, first250PCs)
longMatrix <- matrix(data = long, nrow = 494, ncol = 251)
dataFrameLong <- data.frame(longMatrix)
#dataFrameLong
lmlong = lm(formula = X1 ~ . , data = dataFrameLong)
# size 494 * 251 => first column become the latitude
lat <- c(NAm2$lat, first250PCs)
latMatrix <- matrix(data = lat, nrow = 494, ncol = 251)
dataFrameLat <- data.frame(latMatrix)
dataFrameLat
lmlat = lm(formula = X1 ~ . , data = dataFrameLat)
plot(lmlong$fitted.values,lmlat$fitted.values,col="white")
for (i in 1:npop) {
#print(names[i])
lines(lmlong$fitted.values[which(NAm2[,3]==names[i])],
lmlat$fitted.values[which(NAm2[,3]==names[i])],
type="p",col=colPalette[i],pch=pch[i])
}
legend("bottomleft",legend=names,col=colPalette,lty=-1,pch=pch,cex=.75,ncol=3,lwd=2)

If we compare it to the map from the question 1, we can clearly say that this map represent very optimistically places where population live. It looks quite messy if we just take a look around Panama. However if we examine the estimated places of the Chipewyan, Cree, Ojibwa, Pima and Huiliche populations, we can very distinctly see that the estimation is pretty accurate.
b)
# import the library needed to use rdist.earth
library("fields")
Loading required package: spam
Loading required package: dotCall64
Loading required package: grid
Spam version 2.1-1 (2017-07-02) is loaded.
Type 'help( Spam)' or 'demo( spam)' for a short introduction
and overview of this package.
Help for individual functions is also obtained by adding the
suffix '.spam' to the function name, e.g. 'help( chol.spam)'.
Attaching package: ‘spam’
The following objects are masked from ‘package:base’:
backsolve, forwardsolve
# select the theory latitude and longitude of populations
theoryPosition <- matrix(data = c(NAm2$long, NAm2$lat), nrow = 494, ncol = 2)
#theoryPosition
# vector used to stock the mean of distance for each population
stock <- c()
tmpIndex <- 0
for (i in 1:npop) {
# vector long estimated for population n°i
tmpLong <- lmlong$fitted.values[which(NAm2[,3]==names[i])]
# vector lat estimated for population n°i
tmpLat <- lmlat$fitted.values[which(NAm2[,3]==names[i])]
# matrix of the estimated positions
estimatedPosition <- matrix(data = c(tmpLong, tmpLat), ncol = 2)
#print(estimatedPosition)
len <- length(estimatedPosition)/2
# by making unique we assume that two estimated coordinates will never be at the same exact position
diff <- unique(rdist.earth(x1 = theoryPosition[tmpIndex:(tmpIndex+len), ], x2 = estimatedPosition, miles = F, R = NULL))
# stock the mean of distance from the theorical position in kilometers
stock[i] <- mean(diff)
tmpIndex <- tmpIndex + len
}
plot(c(1:npop), stock, main = "Mean difference in kilometers between theoric and estimated positions",
xlab = "N° associated to the population",
ylab = "Mean of the distance in kilometers")
linearTest <- lm(stock ~ c(1:npop))
abline(linearTest)

Thanks to the previous graph, we can say that the estimated positions are on average approximately \(1100\) kilometers away from the theorical position. It might seem a lot at first sight because it sounds huge if we just have a human sensible approach. Nonetheless it is not really a lot in reality if we size to the scale of the earth. Indeed, we could just think about the fact that the earth’s circonference is equal to \(40075\) kilometers. If we draw a circle around the theorical position for each population, on average, the estimation of the position will be contained inside the circle.
5) PCR and Cross-Validation
a)
Cross-Validation is a technique used in model selection to better estimate the test error of a predictive model. The principle of K-fold cross validation method is to divide randomly the data into K subsets where K-1 subsets are used as the training sets and the remaining subset is used as a validation subset to compute a prediction error. We repeat this procedure K times by considering each subset as the validation subset and the others subsets as the training sets. The procedure is finished when each subset has been used once as the validation subset. The K results from the folds can then be averaged to produce a single estimation.
The advantage of this method is that all observations are used for both training and validation, and each observation is used for validation exactly once.
labels <- rep(1:10, each=10)
set <- sample(labels, 494, replace = TRUE)
set
[1] 5 6 1 3 1 5 8 10 3 8 3 8 2 10 2 2 2 7 6 3 10 2 1 9 4 9 10 1 3 7 6 4 3 2 7
[36] 7 7 8 7 1 2 3 3 4 10 7 10 9 8 6 1 3 8 4 7 4 1 1 5 2 8 5 7 4 7 7 7 10 2 2
[71] 6 3 8 1 7 6 10 2 4 5 3 8 2 10 5 2 3 10 10 7 2 7 9 3 7 3 6 1 10 1 6 8 9 1 6
[106] 1 8 3 5 3 3 7 3 5 2 10 5 9 2 4 6 8 4 5 5 9 4 2 9 10 9 1 10 10 10 6 9 3 10 1
[141] 4 2 2 7 1 9 10 9 8 3 9 6 2 4 5 5 7 6 4 8 8 7 9 9 6 10 6 7 10 1 9 9 5 2 7
[176] 6 5 8 1 2 6 8 8 7 5 5 9 8 10 1 4 2 3 9 2 1 9 2 4 10 6 1 6 4 1 1 8 5 7 9
[211] 7 7 8 5 6 5 4 10 3 6 2 5 4 10 3 6 5 10 6 5 9 10 4 7 5 5 1 9 10 4 2 3 1 4 9
[246] 7 10 4 8 3 1 1 5 5 8 4 6 3 6 4 7 1 8 3 3 3 5 2 4 5 9 6 3 1 4 1 6 8 10 2
[281] 8 1 5 1 2 7 10 3 8 3 2 4 3 4 9 6 1 1 1 2 8 9 4 1 5 10 10 1 5 4 9 2 2 5 9
[316] 8 5 6 9 7 1 1 7 9 8 6 9 10 2 10 3 5 5 6 3 9 4 5 5 10 5 10 10 1 6 10 8 3 4 2
[351] 9 3 1 2 6 1 4 9 2 8 9 4 2 1 10 10 3 10 8 6 4 5 6 7 8 5 8 9 5 8 9 10 4 10 1
[386] 8 9 4 10 2 3 5 1 8 6 10 10 10 2 10 8 2 1 6 3 3 3 8 5 1 2 10 6 10 5 5 8 8 7 6
[421] 7 1 3 4 4 5 3 2 6 8 9 5 1 5 5 8 7 1 3 10 7 3 5 5 2 1 6 1 3 10 9 7 1 1 8
[456] 7 6 9 2 5 6 1 3 7 6 9 2 3 3 8 8 9 5 10 5 6 5 2 2 2 1 1 3 2 1 1 9 1 10 4
[491] 10 9 10 2
b)
naxes <- 4
predictedCoord <- matrix(data = NA, nrow = 494, ncol = 2)
# Regression for the longitude
pcalong <- data.frame(cbind(long=NAm2[,c("long")], pcaNAm2$x[,1:naxes], set))
reglong <- lm(formula = long ~ . , data = subset(pcalong[, 1:5], set != 1))
# Regression for the latitude
pcalat <- data.frame(cbind(lat=NAm2[,c("lat")], pcaNAm2$x[,1:naxes], set))
reglat <- lm(formula = lat ~ . , data = subset(pcalat[, 1:5], set != 1))
# Prediction
# i = 1
predict_long <- predict(reglong, newdata=data.frame(subset(pcalong, set == 1)))
predict_lat <- predict(reglat, newdata=data.frame(subset(pcalat, set == 1)))
idx = 1
for (indice in 1:494) {
if (pcalong[indice, 6] == 1) {
predictedCoord[indice, 1] = predict_long[idx]
predictedCoord[indice, 2] = predict_lat[idx]
idx = idx + 1
}
}
# predictedCoord
for(i in 2:10){
reglong <- lm(formula = long ~ . , data = subset(pcalong[, 1:5], set != i))
reglat <- lm(formula = lat ~ . , data = subset(pcalat[, 1:5], set != i))
predict_long <- predict(reglong, newdata=data.frame(subset(pcalong, set == i)))
predict_lat <- predict(reglat, newdata=data.frame(subset(pcalat, set == i)))
idx = 1
for (j in 1:494) {
if (pcalong[j, 6] == i){
predictedCoord[j, 1] <- predict_long[idx]
predictedCoord[j, 2] <- predict_lat[idx]
idx = idx + 1
}
}
}
# predictedCoord
# Calculation of the prediction error
schtroumph <- rdist.earth(x1 = theoryPosition, x2 = predictedCoord, miles = F, R = NULL)
vect <- schtroumph[1, ]
mean(vect[1:30])
[1] 2289.334
index_vect <- c(1:npop)
indice_main_vect <- 1
index = 1
tmp = NAm2$Pop[1]
for (popName in NAm2$Pop) {
string = popName
if (string != tmp) {
index_vect[indice_main_vect] <- index
indice_main_vect <- indice_main_vect + 1
}
tmp = string
index = index + 1
}
index_vect[npop] <- 494
main_vect <- c(1:npop)
indice1 <- 1
for (indice in 1:npop) {
indice2 <- index_vect[indice]
main_vect[indice] <- mean(vect[indice1:indice2])
indice1 <- indice2
}
stock <- main_vect
stock
[1] 2289.334 3379.760 3541.025 5984.043 5679.188 5844.677 5826.365 7367.050 6671.858 6058.597
[11] 5781.372 6701.283 11418.379 6149.238 6002.236 7543.447 6431.811 5917.866 6884.382 6313.137
[21] 6973.247 5868.110 6697.199 8413.015 9645.011 5494.095 3544.385
plot(c(1:npop), stock, main = "Mean difference in kilometers between theoric and estimated positions",
xlab = "N° associated to the population",
ylab = "Mean of the distance in kilometers")
linearTest <- lm(stock ~ c(1:npop))
abline(linearTest)

c)
for (naxes in 2:440){
}
LS0tCnRpdGxlOiAiVFAyIGdlbmV0aWNEYXRhIE1pbmluZyAtIFBDQS1yZWdyZXNzaW9uIGluIGdlbmV0aWNzIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpMYW15YWEgQk9VWkJJQkEKQWxleGFuZHJlIFBPVVBFQVUKRWxvaXNlIEpVTElFTgoKIyMjIDEuIGdlbmV0aWNEYXRhCgpgYGB7cn0KCk5BbTIgPSByZWFkLnRhYmxlKCJOQW0yLnR4dCIsIGhlYWRlciA9IFRSVUUpCgojIHVuaXF1ZSBpcyB1c2VkIHRvIGdldCB0aGUgbmFtZSBvZiBhbGwgcG9wdWxhdGlvbiAvIGV0aG5pY3Mgd2l0aG91dCBkdXBsaWNhdGVzCm5hbWVzPXVuaXF1ZShOQW0yJFBvcCkKbnBvcD1sZW5ndGgobmFtZXMpCgojIGNvb3JkaW5hdGVzIGZvciBlYWNoIHBvcApjb29yZD11bmlxdWUoTkFtMlssIGMoIlBvcCIsImxvbmciLCJsYXQiKV0pCmNvbFBhbGV0dGU9cmVwKGMoImJsYWNrIiwicmVkIiwiY3lhbiIsIm9yYW5nZSIsImJyb3duIiwiYmx1ZSIsInBpbmsiLCJwdXJwbGUiLCJkYXJrZ3JlZW4iKSwzKQoKIyB0eXBlIDE2ID0gY2lyY2xlIC8gdHlwZSAxNSA9IHNxdWFyZSAvIHR5cGUgMjUgPSB0cmlhbmdsZQpwY2g9cmVwKGMoMTYsMTUsMjUpLGVhY2g9OSkKCiMgdGhlIGRpc3BsYXkgd29ya3MgYmVjYXVzZSBmb3IgZWFjaCBwb3B1bGF0aW9uIHdlIGhhdmUgdGhlIGxhdGl0dWRlIGFuZCB0aGUgbG9uZ2l0dWRlCnBsb3QoY29vcmRbLCBjKCJsb25nIiwibGF0IildLHBjaD1wY2gsY29sPWNvbFBhbGV0dGUsYXNwPTEpCgojIGFzcCBhbGxvd3MgdG8gaGF2ZSB0aGUgY29ycmVjdCByYXRpbyBiZXR3ZWVuICBheGlzICBsb25naXR1ZGUgYW5kIGxhdGl0dWRlCiMgVGhlbiB0aGUgbWFwIGlzIG5vdCBkZWZvcm1lZCAgCmxlZ2VuZCgiYm90dG9tbGVmdCIsbGVnZW5kPW5hbWVzLGNvbD1jb2xQYWxldHRlLGx0eT0tMSxwY2g9cGNoLGNleD0uNzUsbmNvbD0yLGx3ZD0yKQoKbGlicmFyeShtYXBzKTttYXAoIndvcmxkIixhZGQ9VCkKCgpgYGAKClRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgc2NyaXB0IGlzIGluIHRoZSBjb21tZW50YXJpZXMgYWJvdmUuCgojIyMgMi4gUmVncmVzc2lvbgoKYGBge3J9CgojIHR1cm4gdGhlIG1hdHJpeCBpbnRvIGEgZ2VuZXRpY0RhdGEgZnJhbWUKZ2VuZXRpY0RhdGEgPSBOQW0yWywtYygxOjcpXQoKZ2VuZXRpY0RhdGFGcmFtZSA9IGRhdGEuZnJhbWUoZ2VuZXRpY0RhdGEpCgojIGNyZWF0aW9uIG9mIHRoZSBsaW5lYXIgbW9kZWwKcmVnID0gbG0oZm9ybXVsYSA9IGxvbmcgfiAuICwgZGF0YSA9IGdlbmV0aWNEYXRhRnJhbWUpCgojIHVuY29tbWVudCB0aGF0IGZvbGxvd2luZyBwYXJ0IHRvIHNlZSB0aGUgc3VtbWFyeSBvZiB0aGUgcmVncmVzc2lvbgojIHN1bW1hcnkocmVnKQoKYGBgCgpBbGwgdmFsdWVzIGFyZSBOQSAoTm90IEF2YWlsYWJsZSkgYmVjYXVzZSB3ZSBoYXZlIHRvbyBtdWNoIHByZWRpY3RvcnMuIFRoZSAkWCQgbWF0cml4IGlzIGNhbm5vdCBiZSByZXZlcnNlZCBzbyB3ZSBoYXZlIHRvIHVzZSB0aGUgUENBIG1ldGhvZCB0byBjb3VudGVyIHRoYXQgcHJvYmxlbS4KCiMjIyAzLlBDQSBQcmluY2lwYWwgQ29tcG9uZW50IEFuYWx5c2lzCgojIyMjIGEpIAoKVGhlIG1haW4gZ29hbCBvZiB0aGUgUENBIGlzIHRvIHJlZHVjZSB0aGUgbnVtYmVyIG9mIHByZWRpY3RvcnMuIEluIG9yZGVyIHRvIGFjaGlldmUgdGhhdCwgd2UgaGF2ZSB0byBleHRyYWN0IHRoZSBtb3N0IGltcG9ydGFudCBjb21wb25lbnRzIG9mIHRoZSBnZW5ldGljRGF0YSBzZXQuIFRoZXNlIG5ldyB2YXJpYWJsZXMgYXJlIGEgbGluZWFyIGNvbWJpbmFpc29uIG9mIHRoZSBvcmlnaW5hbCBvbmVzLiBUaGUgbnVtYmVyIG9mIHByaW5jaXBhbCBjb21wb25lbnRzIGlzIHNtYWxsZXIgdGhhbiB0aGUgbnVtYmVyIG9mIG9yaWdpbmFsIHZhcmlhYmxlcy4gVGhlIGFpbSBpcyB0byBtYXhpbWl6ZSB0aGUgdmFyaWF0aW9uIG9mIHRoZSBnZW5ldGljRGF0YSBzZXQuCgojIyMjIGIpCgpgYGB7cn0KCiMgaW5zdGFsbC5wYWNrYWdlcygiZmFjdG9leHRyYSIpCgpsaWJyYXJ5KGZhY3RvZXh0cmEpCgphbGxHZW5lcyA8LSBnZW5ldGljRGF0YUZyYW1lWywgLTFdCgpwY2FOQW0yIDwtIHByY29tcChhbGxHZW5lcywgc2NhbGUgPSBGQUxTRSkKCmZ2aXpfZWlnKHBjYU5BbTIpCgp2ZWN0UHJvcG9ydGlvbk9mVmFyaWFuY2UgPC0gcGNhTkFtMiRzZGV2XjIvc3VtKHBjYU5BbTIkc2Rldl4yKQoKIyBzdW1tYXJ5KHBjYU5BbTIucGNhKQoKCmBgYAoKSXQgaXMgYmV0dGVyIHRvIHVzZSBzY2FsZSA9IEZBTFNFIGJ5IGNvbnZlbnRpb24gYmVjYXVzZSB3ZSBnZXQgYSBiZXR0ZXIgcmVwcmVzZW50YXRpb24gb2YgdGhlIHBlcmNlbnRhZ2Ugb2YgZXhwbGFpbmVkIHZhbHVlcy4KCkZBTFNFIDogNDk0ID0gbGluZWFyIGNvbWJpYW5pc29uIG9mIHRoZSA1MDAwIGdlbmVzCldlIG5vdGljZSB0aGF0IHdlIGdldCBvbmx5IDQ5NCBwcmluY2lwYWwgY29tcG9uZW50cyBpbnN0ZWFkIG9mIGFwcHJveGltYXRlbHkgNTAwMCB3aGljaCBjb3JyZXNwb25kIHRvIHRoZSBudW1iZXIgb2YgZ2VuZXMuIFRoaXMgY2FuIGJlIGV4cGxhaW5lZCBiZWNhdXNlICIiIGluIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCB0aGUgZWlnZW52YWx1ZXMgZnJvbSA0OTUgdG8gfjUwMDAgYXJlIGVxdWFscyB0byB6ZXJvLiBJbiByZWFsaXR5LCB3ZSBvbmx5IHNlbGVjdCB0aGUgZ2VuZXMgdGhhdCBiZXN0IGV4cGxhaW4gdGhlIG1vZGVsIHVwIHRvIDUwMC4gSWYgd2UgaGFkIHRvIHJlYWxseSBmaW5kIHRoZSAiYmVzdC1leHBsYWluaW5nIiwgd2hpY2ggbWVhbnMgZmluZGluZyB0aGUgbW9zdCBleHBsaWNhdGl2ZSBnZW5lcyBmcm9tIDEgdG8gNTAwMCB3ZSB3b3VsZCBoYXZlIHRvIHRlc3QgYWxsIHRoZSBjb21iaW5haXNvbnMgb2YgNDk0IGdlbmVzLiAgIAoKIyMjIyBjKQoKYGBge3J9CgpjYXhlcz1jKDEsMikKcGxvdChwY2FOQW0yJHhbLGNheGVzXSxjb2w9IndoaXRlIikKCmZvciAoaSBpbiAxOm5wb3ApIHsKICAjIHByaW50KG5hbWVzW2ldKQogIGxpbmVzKHBjYU5BbTIkeFt3aGljaChOQW0yWywzXT09bmFtZXNbaV0pLGNheGVzXSwKICB0eXBlPSJwIixjb2w9Y29sUGFsZXR0ZVtpXSxwY2g9cGNoW2ldKQp9CmxlZ2VuZCgidG9wbGVmdCIsbGVnZW5kPW5hbWVzLGNvbD1jb2xQYWxldHRlLGx0eT0tCjEscGNoPXBjaCxjZXg9LjY1LG5jb2w9Myxsd2Q9MikKCmNheGVzPWMoNSw2KQpwbG90KHBjYU5BbTIkeFssY2F4ZXNdLGNvbD0id2hpdGUiKQoKZm9yIChpIGluIDE6bnBvcCkgewogICMgcHJpbnQobmFtZXNbaV0pCiAgbGluZXMocGNhTkFtMiR4W3doaWNoKE5BbTJbLDNdPT1uYW1lc1tpXSksY2F4ZXNdLAogIHR5cGU9InAiLGNvbD1jb2xQYWxldHRlW2ldLHBjaD1wY2hbaV0pCn0KbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPW5hbWVzLGNvbD1jb2xQYWxldHRlLGx0eT0tCjEscGNoPXBjaCxjZXg9LjY1LG5jb2w9Myxsd2Q9MikKCmBgYAoKVGhlIEFjaGUgcG9wdWxhdGlvbiBpcyB3ZWxsIGlkZW50aWZpZWQgYnkgYm90aCBjb21wb25lbnRzLiBUaGUgU3VydWkgY2FuIGFsc28gYmUgaWRlbnRpZmllZCBieSBib3RoIGNvbXBvbmVudHMgYnV0IG1vcmUgZXNwZWNpYWxseSBieSB0aGUgUEMxLgoKVGhlIEthcml0aWFuYSBwb3B1bGF0aW9uIGlzIHdlbGwgaWRlbnRpZmllZCBieSB0aGUgUEM1LiBUaGUgUGltYSBwb3B1bGF0aW9uIGlzIHdlbGwgaWRlbnRpZmllZCBieSB0aGUgUEM2LgoKIyMjIyBkKQoKCmBgYHtyfQoKaW5lcnRpYSA9IHZlY3RQcm9wb3J0aW9uT2ZWYXJpYW5jZVsxXSArIHZlY3RQcm9wb3J0aW9uT2ZWYXJpYW5jZVsyXQoKc3ByaW50ZigiVGhlIGluZXJ0aWEgaXMgZXF1YWwgdG8gJWYuIiwgaW5lcnRpYSkKCmBgYAoKCkFjY29yZGluZyB0byB3aGF0IHdlIGhhdmUgc2VlbiB1bnRpbCBub3csIHdlIGhhdmUgdHdvIGlkZWFzLgoKVGhlIGZpcnN0IGlkZWEgaXMgdGhhdCB3ZSBoYXZlIHNlZW4gdGhhdCB3ZSBjYW4gZGlzdGluZ3Vpc2ggdHdvIHBvcHVsYXRpb24gdXNpbmcgdHdvIHByaW5jaXBhbCBjb21wb25lbnRzLiBUaGVyZWZvcmUsIGFzIHRoZXJlIGFyZSAyNyBkaWZmZXJlbnQgcG9wdWxhdGlvbnMsIHdlIGNvdWxkIGRlZHVjZSB0aGF0IHdlIHdvdWxkIG5lZWQgMTQgcGFpcnMgb2YgcHJpbmNpcGFsIGNvbXBvbmVudHMuIAoKSG93ZXZlciwgd2UgY2FuIGFzayBvdXJzZWx2ZXMgaWYgd2UgY2FuIHJlYWxseSBlYWNoIHRpbWUgZGlzdGluZ3Vpc2ggdHdvIGRpZmZlcmVudCBwb3B1bGF0aW9ucyB1c2luZyB0d28gcHJpbmNpcGFsIGNvbXBvbmVudHMuIEl0IG1pZ2h0IG5vdCBiZSB0aGUgY2FzZSBiZWNhdXNlIHdlIGhhdmUganVzdCB0ZXN0ZWQgaXQgd2l0aCB0d28gcGFpcnMgb2YgcHJpbmNpcGFsIGNvbXBvbmVudHMuIFRodXMsIHdlIGNvdWxkIHRoaW5rIGFib3V0IGFuIGFsdGVybmF0aXZlIHdheSwgd2hpY2ggaXMgYWRkaW5nIHRoZSB2YXJpYW5jZSBvZiB0aGUgZmlyc3QgcHJpbmNpcGFsIGNvbXBvbmVudHMgdW50aWwgdGhlIHN1bSBpcyBlcXVhbCB0byBhIGNlcnRhaW4gbGV2ZWwuIFRoaXMgbGV2ZWwgY291bGQgYmUgMjUlIG9yIDUwJS4gVGhpcyBsYXN0IG9uZSBtZWFucyB1c2luZyBhIGxvdCBvZiBwcmluY2lwYWwgY29tcG9uZW50cy4gCgpgYGB7cn0KCm51bWJlck9mUENzIDwtIGZ1bmN0aW9uKHZlY3RvclByb3BvcnRpb25PZlZhcmlhbmNlLCBwZXJjZW50YWdlKSB7CiAgdG1wID0gMC4wCiAgaSA9IDEKICB3aGlsZSAodG1wIDwgcGVyY2VudGFnZSkgewogICAgdG1wID0gdG1wICsgdmVjdFByb3BvcnRpb25PZlZhcmlhbmNlW2ldCiAgICBpID0gaSArIDEKICB9CiAgcmV0dXJuKGkpCn0KCm5iclBDMjUgPC0gbnVtYmVyT2ZQQ3ModmVjdFByb3BvcnRpb25PZlZhcmlhbmNlLCAwLjI1KQpuYnJQQzUwIDwtIG51bWJlck9mUENzKHZlY3RQcm9wb3J0aW9uT2ZWYXJpYW5jZSwgMC41KQpuYnJQQzc1IDwtIG51bWJlck9mUENzKHZlY3RQcm9wb3J0aW9uT2ZWYXJpYW5jZSwgMC43NSkKbmJyUEM5OSA8LSBudW1iZXJPZlBDcyh2ZWN0UHJvcG9ydGlvbk9mVmFyaWFuY2UsIDAuOTkpCgpzcHJpbnRmKCJOdW1iZXIgb2YgcHJpbmNpcGFsIGNvbXBvbmVudHMgbmVlZGVkIGluIG9yZGVyIHRvIGNvdmVyIGF0IGxlYXN0IDI1IHBlcmNlbnQgb2YgdmFyaWFuY2UgOiAlaSIsIG5iclBDMjUpCnNwcmludGYoIk51bWJlciBvZiBwcmluY2lwYWwgY29tcG9uZW50cyBuZWVkZWQgaW4gb3JkZXIgdG8gY292ZXIgYXQgbGVhc3QgNTAgcGVyY2VudCBvZiB2YXJpYW5jZSA6ICVpIiwgbmJyUEM1MCkKc3ByaW50ZigiTnVtYmVyIG9mIHByaW5jaXBhbCBjb21wb25lbnRzIG5lZWRlZCBpbiBvcmRlciB0byBjb3ZlciBhdCBsZWFzdCA3NSBwZXJjZW50IG9mIHZhcmlhbmNlIDogJWkiLCBuYnJQQzc1KQpzcHJpbnRmKCJOdW1iZXIgb2YgcHJpbmNpcGFsIGNvbXBvbmVudHMgbmVlZGVkIGluIG9yZGVyIHRvIGNvdmVyIGF0IGxlYXN0IDk5IHBlcmNlbnQgb2YgdmFyaWFuY2UgOiAlaSIsIG5iclBDOTkpCgpgYGAKCldpdGggdGhlIHRlc3Qgd2UgaGF2ZSBlc3RhYmxpc2hlZCBqdXN0IGJlZm9yZSB3ZSBjYW4gc2VlIHRoYXQgbGVzcyB0aGFuICQxLzEwJCAgb2YgdGhlIGRhdGEgY29udGFpbnMgJDI1JSQgb2YgdGhlIHZhcmlhbmNlIDogU28gaXQgc2VlbXMgbGlrZSBhIGdvb2QgaWRlYSB0byB1c2Ugb25seSAkNTAkIFBDIHRvIGdldCBtb3N0IG9mIHRoZSBpbmZvcm1hdGlvbiB3aXRoaW4gbGVhc3QgZGF0YS4gU28gd2UgbWlnaHQgdXNlIHRoYXQgbnVtYmVyIG9mIFBDIGluIG9yZGVyIHRvIHJlcHJlc2VudCBnZW5ldGljIG1hcmtlcnMuClRoZSBvdGhlciBudW1iZXJzIGdpdmUgYSBpZGVhIG9mIHRoZSBudW1iZXIgbmVlZGVkIGlmIHdlIHdhbnQgdG8gY292ZXIgbW9yZSBpbmZvcm1hdGlvbi4KCiMjIyA0LiBQQ1IgUHJpbmNpcGFsIENvbXBvbmVudHMgUmVncmVzc2lvbgoKIyMjIyBhKQoKYGBge3J9CgojIHBjYU5BbTIkeCBhcmUgc2NvcmVzIDogc2l6ZSA0OTQgKiA0OTQgbWF0cml4LiBXZSB0YWtlIGFsbCB0aGUgbGlnbnMgYnV0IG9ubHkgMjUwIGNvbHVtbnMKZmlyc3QyNTBQQ3MgPC0gcGNhTkFtMiR4WywgYygxOjI1MCldCgojIHNpemUgNDk0ICogMjUxID0+IGZpcnN0IGNvbHVtbiBiZWNvbWUgdGhlIGxvbmdpdHVkZQpsb25nIDwtIGMoTkFtMiRsb25nLCBmaXJzdDI1MFBDcykKbG9uZ01hdHJpeCA8LSBtYXRyaXgoZGF0YSA9IGxvbmcsIG5yb3cgPSA0OTQsIG5jb2wgPSAyNTEpCmRhdGFGcmFtZUxvbmcgPC0gZGF0YS5mcmFtZShsb25nTWF0cml4KQojZGF0YUZyYW1lTG9uZwpsbWxvbmcgPSBsbShmb3JtdWxhID0gWDEgfiAuICwgZGF0YSA9IGRhdGFGcmFtZUxvbmcpCgojIHNpemUgNDk0ICogMjUxID0+IGZpcnN0IGNvbHVtbiBiZWNvbWUgdGhlIGxhdGl0dWRlCmxhdCA8LSBjKE5BbTIkbGF0LCBmaXJzdDI1MFBDcykKbGF0TWF0cml4IDwtIG1hdHJpeChkYXRhID0gbGF0LCBucm93ID0gNDk0LCBuY29sID0gMjUxKQpkYXRhRnJhbWVMYXQgPC0gZGF0YS5mcmFtZShsYXRNYXRyaXgpCmRhdGFGcmFtZUxhdApsbWxhdCA9IGxtKGZvcm11bGEgPSBYMSB+IC4gLCBkYXRhID0gZGF0YUZyYW1lTGF0KQoKcGxvdChsbWxvbmckZml0dGVkLnZhbHVlcyxsbWxhdCRmaXR0ZWQudmFsdWVzLGNvbD0id2hpdGUiKQoKZm9yIChpIGluIDE6bnBvcCkgewogICNwcmludChuYW1lc1tpXSkKICBsaW5lcyhsbWxvbmckZml0dGVkLnZhbHVlc1t3aGljaChOQW0yWywzXT09bmFtZXNbaV0pXSwKICAgICAgICBsbWxhdCRmaXR0ZWQudmFsdWVzW3doaWNoKE5BbTJbLDNdPT1uYW1lc1tpXSldLAogICAgICAgIHR5cGU9InAiLGNvbD1jb2xQYWxldHRlW2ldLHBjaD1wY2hbaV0pCn0KCmxlZ2VuZCgiYm90dG9tbGVmdCIsbGVnZW5kPW5hbWVzLGNvbD1jb2xQYWxldHRlLGx0eT0tMSxwY2g9cGNoLGNleD0uNzUsbmNvbD0zLGx3ZD0yKQoKCmBgYAoKSWYgd2UgY29tcGFyZSBpdCB0byB0aGUgbWFwIGZyb20gdGhlIHF1ZXN0aW9uIDEsIHdlIGNhbiBjbGVhcmx5IHNheSB0aGF0IHRoaXMgbWFwIHJlcHJlc2VudCB2ZXJ5IG9wdGltaXN0aWNhbGx5IHBsYWNlcyB3aGVyZSBwb3B1bGF0aW9uIGxpdmUuIEl0IGxvb2tzIHF1aXRlIG1lc3N5IGlmIHdlIGp1c3QgdGFrZSBhIGxvb2sgYXJvdW5kIFBhbmFtYS4gSG93ZXZlciBpZiB3ZSBleGFtaW5lIHRoZSBlc3RpbWF0ZWQgcGxhY2VzIG9mIHRoZSBDaGlwZXd5YW4sIENyZWUsIE9qaWJ3YSwgUGltYSBhbmQgSHVpbGljaGUgcG9wdWxhdGlvbnMsIHdlIGNhbiB2ZXJ5IGRpc3RpbmN0bHkgc2VlIHRoYXQgdGhlIGVzdGltYXRpb24gaXMgcHJldHR5IGFjY3VyYXRlLgoKIyMjIyBiKSAKCmBgYHtyfQoKIyBpbXBvcnQgdGhlIGxpYnJhcnkgbmVlZGVkIHRvIHVzZSByZGlzdC5lYXJ0aApsaWJyYXJ5KCJmaWVsZHMiKQoKIyBzZWxlY3QgdGhlIHRoZW9yeSBsYXRpdHVkZSBhbmQgbG9uZ2l0dWRlIG9mIHBvcHVsYXRpb25zCnRoZW9yeVBvc2l0aW9uIDwtIG1hdHJpeChkYXRhID0gYyhOQW0yJGxvbmcsIE5BbTIkbGF0KSwgbnJvdyA9IDQ5NCwgbmNvbCA9IDIpCiN0aGVvcnlQb3NpdGlvbgoKIyB2ZWN0b3IgdXNlZCB0byBzdG9jayB0aGUgbWVhbiBvZiBkaXN0YW5jZSBmb3IgZWFjaCBwb3B1bGF0aW9uCnN0b2NrIDwtIGMoKQoKdG1wSW5kZXggPC0gMApmb3IgKGkgaW4gMTpucG9wKSB7CiAgIyB2ZWN0b3IgbG9uZyBlc3RpbWF0ZWQgZm9yIHBvcHVsYXRpb24gbsKwaQogIHRtcExvbmcgPC0gbG1sb25nJGZpdHRlZC52YWx1ZXNbd2hpY2goTkFtMlssM109PW5hbWVzW2ldKV0KICAKICAjIHZlY3RvciBsYXQgZXN0aW1hdGVkIGZvciBwb3B1bGF0aW9uIG7CsGkKICB0bXBMYXQgPC0gbG1sYXQkZml0dGVkLnZhbHVlc1t3aGljaChOQW0yWywzXT09bmFtZXNbaV0pXQogIAogICMgbWF0cml4IG9mIHRoZSBlc3RpbWF0ZWQgcG9zaXRpb25zCiAgZXN0aW1hdGVkUG9zaXRpb24gPC0gbWF0cml4KGRhdGEgPSBjKHRtcExvbmcsIHRtcExhdCksIG5jb2wgPSAyKQogICNwcmludChlc3RpbWF0ZWRQb3NpdGlvbikKICAKICBsZW4gPC0gbGVuZ3RoKGVzdGltYXRlZFBvc2l0aW9uKS8yCiAgCiAgIyBieSBtYWtpbmcgdW5pcXVlIHdlIGFzc3VtZSB0aGF0IHR3byBlc3RpbWF0ZWQgY29vcmRpbmF0ZXMgd2lsbCBuZXZlciBiZSBhdCB0aGUgc2FtZSBleGFjdCBwb3NpdGlvbgogIGRpZmYgPC0gdW5pcXVlKHJkaXN0LmVhcnRoKHgxID0gdGhlb3J5UG9zaXRpb25bdG1wSW5kZXg6KHRtcEluZGV4K2xlbiksIF0sIHgyID0gZXN0aW1hdGVkUG9zaXRpb24sIG1pbGVzID0gRiwgUiA9IE5VTEwpKQogIAogICMgc3RvY2sgdGhlIG1lYW4gb2YgZGlzdGFuY2UgZnJvbSB0aGUgdGhlb3JpY2FsIHBvc2l0aW9uIGluIGtpbG9tZXRlcnMKICBzdG9ja1tpXSA8LSBtZWFuKGRpZmYpCiAgCiAgdG1wSW5kZXggPC0gdG1wSW5kZXggKyBsZW4KfQoKcGxvdChjKDE6bnBvcCksIHN0b2NrLCBtYWluID0gIk1lYW4gZGlmZmVyZW5jZSBpbiBraWxvbWV0ZXJzIGJldHdlZW4gdGhlb3JpYyBhbmQgZXN0aW1hdGVkIHBvc2l0aW9ucyIsCiAgICAgeGxhYiA9ICJOwrAgYXNzb2NpYXRlZCB0byB0aGUgcG9wdWxhdGlvbiIsIAogICAgIHlsYWIgPSAiTWVhbiBvZiB0aGUgZGlzdGFuY2UgaW4ga2lsb21ldGVycyIpCmxpbmVhclRlc3QgPC0gbG0oc3RvY2sgfiBjKDE6bnBvcCkpCmFibGluZShsaW5lYXJUZXN0KQoKYGBgCgpUaGFua3MgdG8gdGhlIHByZXZpb3VzIGdyYXBoLCB3ZSBjYW4gc2F5IHRoYXQgdGhlIGVzdGltYXRlZCBwb3NpdGlvbnMgYXJlIG9uIGF2ZXJhZ2UgYXBwcm94aW1hdGVseSAkMTEwMCQga2lsb21ldGVycyBhd2F5IGZyb20gdGhlIHRoZW9yaWNhbCBwb3NpdGlvbi4gSXQgbWlnaHQgc2VlbSBhIGxvdCBhdCBmaXJzdCBzaWdodCBiZWNhdXNlIGl0IHNvdW5kcyBodWdlIGlmIHdlIGp1c3QgaGF2ZSBhIGh1bWFuIHNlbnNpYmxlIGFwcHJvYWNoLiBOb25ldGhlbGVzcyBpdCBpcyBub3QgcmVhbGx5IGEgbG90IGluIHJlYWxpdHkgaWYgd2Ugc2l6ZSB0byB0aGUgc2NhbGUgb2YgdGhlIGVhcnRoLiBJbmRlZWQsIHdlIGNvdWxkIGp1c3QgdGhpbmsgYWJvdXQgdGhlIGZhY3QgdGhhdCB0aGUgZWFydGgncyBjaXJjb25mZXJlbmNlIGlzIGVxdWFsIHRvICQ0MDA3NSQga2lsb21ldGVycy4gSWYgd2UgZHJhdyBhIGNpcmNsZSBhcm91bmQgdGhlIHRoZW9yaWNhbCBwb3NpdGlvbiBmb3IgZWFjaCBwb3B1bGF0aW9uLCBvbiBhdmVyYWdlLCB0aGUgZXN0aW1hdGlvbiBvZiB0aGUgcG9zaXRpb24gd2lsbCBiZSBjb250YWluZWQgaW5zaWRlIHRoZSBjaXJjbGUuICAgIAoKCiMjIyA1KSBQQ1IgYW5kIENyb3NzLVZhbGlkYXRpb24KCiMjIyMgYSkKCkNyb3NzLVZhbGlkYXRpb24gaXMgYSB0ZWNobmlxdWUgdXNlZCBpbiBtb2RlbCBzZWxlY3Rpb24gdG8gYmV0dGVyIGVzdGltYXRlIHRoZSB0ZXN0IGVycm9yIG9mIGEgcHJlZGljdGl2ZSBtb2RlbC4gVGhlIHByaW5jaXBsZSBvZiBLLWZvbGQgY3Jvc3MgdmFsaWRhdGlvbiBtZXRob2QgaXMgdG8gZGl2aWRlIHJhbmRvbWx5IHRoZSBkYXRhIGludG8gSyBzdWJzZXRzIHdoZXJlIEstMSBzdWJzZXRzIGFyZSB1c2VkIGFzIHRoZSB0cmFpbmluZyBzZXRzIGFuZCB0aGUgcmVtYWluaW5nIHN1YnNldCBpcyB1c2VkIGFzIGEgdmFsaWRhdGlvbiBzdWJzZXQgdG8gY29tcHV0ZSBhIHByZWRpY3Rpb24gZXJyb3IuIFdlIHJlcGVhdCB0aGlzIHByb2NlZHVyZSBLIHRpbWVzIGJ5IGNvbnNpZGVyaW5nIGVhY2ggc3Vic2V0IGFzIHRoZSB2YWxpZGF0aW9uIHN1YnNldCBhbmQgdGhlIG90aGVycyBzdWJzZXRzIGFzIHRoZSB0cmFpbmluZyBzZXRzLiBUaGUgcHJvY2VkdXJlIGlzIGZpbmlzaGVkIHdoZW4gZWFjaCBzdWJzZXQgaGFzIGJlZW4gdXNlZCBvbmNlIGFzIHRoZSB2YWxpZGF0aW9uIHN1YnNldC4gVGhlIEsgcmVzdWx0cyBmcm9tIHRoZSBmb2xkcyBjYW4gdGhlbiBiZSBhdmVyYWdlZCB0byBwcm9kdWNlIGEgc2luZ2xlIGVzdGltYXRpb24uCgpUaGUgYWR2YW50YWdlIG9mIHRoaXMgbWV0aG9kIGlzIHRoYXQgYWxsIG9ic2VydmF0aW9ucyBhcmUgdXNlZCBmb3IgYm90aCB0cmFpbmluZyBhbmQgdmFsaWRhdGlvbiwgYW5kIGVhY2ggb2JzZXJ2YXRpb24gaXMgdXNlZCBmb3IgdmFsaWRhdGlvbiBleGFjdGx5IG9uY2UuCgpgYGB7cn0KCmxhYmVscyA8LSByZXAoMToxMCwgZWFjaD0xMCkKc2V0IDwtIHNhbXBsZShsYWJlbHMsIDQ5NCwgcmVwbGFjZSA9IFRSVUUpCnNldAoKYGBgCgojIyMjIGIpCgpgYGB7cn0KCm5heGVzIDwtIDQKcHJlZGljdGVkQ29vcmQgPC0gbWF0cml4KGRhdGEgPSBOQSwgbnJvdyA9IDQ5NCwgbmNvbCA9IDIpCgojIFJlZ3Jlc3Npb24gZm9yIHRoZSBsb25naXR1ZGUKcGNhbG9uZyA8LSBkYXRhLmZyYW1lKGNiaW5kKGxvbmc9TkFtMlssYygibG9uZyIpXSwgcGNhTkFtMiR4WywxOm5heGVzXSwgc2V0KSkKCnJlZ2xvbmcgPC0gbG0oZm9ybXVsYSA9IGxvbmcgfiAuICwgZGF0YSA9IHN1YnNldChwY2Fsb25nWywgMTo1XSwgc2V0ICE9IDEpKQoKIyBSZWdyZXNzaW9uIGZvciB0aGUgbGF0aXR1ZGUKcGNhbGF0IDwtIGRhdGEuZnJhbWUoY2JpbmQobGF0PU5BbTJbLGMoImxhdCIpXSwgcGNhTkFtMiR4WywxOm5heGVzXSwgc2V0KSkKCnJlZ2xhdCA8LSBsbShmb3JtdWxhID0gbGF0IH4gLiAsIGRhdGEgPSBzdWJzZXQocGNhbGF0WywgMTo1XSwgc2V0ICE9IDEpKQoKCiMgUHJlZGljdGlvbgojIGkgPSAxCnByZWRpY3RfbG9uZyA8LSBwcmVkaWN0KHJlZ2xvbmcsIG5ld2RhdGE9ZGF0YS5mcmFtZShzdWJzZXQocGNhbG9uZywgc2V0ID09IDEpKSkKcHJlZGljdF9sYXQgPC0gcHJlZGljdChyZWdsYXQsIG5ld2RhdGE9ZGF0YS5mcmFtZShzdWJzZXQocGNhbGF0LCBzZXQgPT0gMSkpKQoKaWR4ID0gMQpmb3IgKGluZGljZSBpbiAxOjQ5NCkgewogIAogIGlmIChwY2Fsb25nW2luZGljZSwgNl0gPT0gMSkgewogICAgCiAgICBwcmVkaWN0ZWRDb29yZFtpbmRpY2UsIDFdID0gcHJlZGljdF9sb25nW2lkeF0KICAgIHByZWRpY3RlZENvb3JkW2luZGljZSwgMl0gPSBwcmVkaWN0X2xhdFtpZHhdCiAgICBpZHggPSBpZHggKyAxCiAgfQogIAp9CgojIHByZWRpY3RlZENvb3JkCgpgYGAKCgoKYGBge3J9Cgpmb3IoaSBpbiAyOjEwKXsKICAgIAogICAgcmVnbG9uZyA8LSBsbShmb3JtdWxhID0gbG9uZyB+IC4gLCBkYXRhID0gc3Vic2V0KHBjYWxvbmdbLCAxOjVdLCBzZXQgIT0gaSkpCiAgICByZWdsYXQgPC0gbG0oZm9ybXVsYSA9IGxhdCB+IC4gLCBkYXRhID0gc3Vic2V0KHBjYWxhdFssIDE6NV0sIHNldCAhPSBpKSkKICAgIAogICAgcHJlZGljdF9sb25nIDwtIHByZWRpY3QocmVnbG9uZywgbmV3ZGF0YT1kYXRhLmZyYW1lKHN1YnNldChwY2Fsb25nLCBzZXQgPT0gaSkpKQogICAgcHJlZGljdF9sYXQgPC0gcHJlZGljdChyZWdsYXQsIG5ld2RhdGE9ZGF0YS5mcmFtZShzdWJzZXQocGNhbGF0LCBzZXQgPT0gaSkpKQogICAgCiAgICBpZHggPSAxCiAgICBmb3IgKGogaW4gMTo0OTQpIHsKICAgICAgCiAgICAgIGlmIChwY2Fsb25nW2osIDZdID09IGkpewogICAgICAKICAgICAgICBwcmVkaWN0ZWRDb29yZFtqLCAxXSA8LSBwcmVkaWN0X2xvbmdbaWR4XQogICAgICAgIHByZWRpY3RlZENvb3JkW2osIDJdIDwtIHByZWRpY3RfbGF0W2lkeF0KICAgICAgICBpZHggPSBpZHggKyAxCiAgICAgICAgCiAgICAgIH0KICAgICAgCiAgICB9CiAgICAKfQoKIyBwcmVkaWN0ZWRDb29yZAoKCiMgQ2FsY3VsYXRpb24gb2YgdGhlIHByZWRpY3Rpb24gZXJyb3IKCmBgYAoKCgpgYGB7cn0KCnNjaHRyb3VtcGggPC0gcmRpc3QuZWFydGgoeDEgPSB0aGVvcnlQb3NpdGlvbiwgeDIgPSBwcmVkaWN0ZWRDb29yZCwgbWlsZXMgPSBGLCBSID0gTlVMTCkKCnZlY3QgPC0gc2NodHJvdW1waFsxLCBdCm1lYW4odmVjdFsxOjMwXSkKCmluZGV4X3ZlY3QgPC0gYygxOm5wb3ApCgppbmRpY2VfbWFpbl92ZWN0IDwtIDEKaW5kZXggPSAxCnRtcCA9IE5BbTIkUG9wWzFdCmZvciAocG9wTmFtZSBpbiBOQW0yJFBvcCkgewogIAogIHN0cmluZyA9IHBvcE5hbWUKICAKICBpZiAoc3RyaW5nICE9IHRtcCkgewogICAgaW5kZXhfdmVjdFtpbmRpY2VfbWFpbl92ZWN0XSA8LSBpbmRleAogICAgaW5kaWNlX21haW5fdmVjdCA8LSBpbmRpY2VfbWFpbl92ZWN0ICsgMQogIH0KICAKICB0bXAgPSBzdHJpbmcKICBpbmRleCA9IGluZGV4ICsgMQp9CgppbmRleF92ZWN0W25wb3BdIDwtIDQ5NAptYWluX3ZlY3QgPC0gYygxOm5wb3ApCmluZGljZTEgPC0gMQpmb3IgKGluZGljZSBpbiAxOm5wb3ApIHsKICAKICBpbmRpY2UyIDwtIGluZGV4X3ZlY3RbaW5kaWNlXQogIG1haW5fdmVjdFtpbmRpY2VdIDwtIG1lYW4odmVjdFtpbmRpY2UxOmluZGljZTJdKQogIGluZGljZTEgPC0gaW5kaWNlMgogIAp9CgpzdG9jayA8LSBtYWluX3ZlY3QKc3RvY2sKCnBsb3QoYygxOm5wb3ApLCBzdG9jaywgbWFpbiA9ICJNZWFuIGRpZmZlcmVuY2UgaW4ga2lsb21ldGVycyBiZXR3ZWVuIHRoZW9yaWMgYW5kIGVzdGltYXRlZCBwb3NpdGlvbnMiLAogICAgIHhsYWIgPSAiTsKwIGFzc29jaWF0ZWQgdG8gdGhlIHBvcHVsYXRpb24iLCAKICAgICB5bGFiID0gIk1lYW4gb2YgdGhlIGRpc3RhbmNlIGluIGtpbG9tZXRlcnMiKQpsaW5lYXJUZXN0IDwtIGxtKHN0b2NrIH4gYygxOm5wb3ApKQphYmxpbmUobGluZWFyVGVzdCkKCgpgYGAKCiMjIyMgYykKCmBgYHtyfQoKZm9yIChuYXhlcyBpbiAyOjQ0MCl7CiAgCn0KCmBgYAoKCgoKCg==